算法选修课作业7, 8… 12

标签（空格分隔）： algorithm homework

[TOC]

Chapter3 Decompositions of graphs

Problem 3.7

(a) 基本思想就是在对 $G$ 的 DFS 过程中对所有的顶点着red, green两种颜色. 在 DFS 生成的搜索树中, 设后继节点的颜色与前驱节点的颜色相反. 对图跑完一遍 DFS后 , 所有节点都被着色. 这样得到的每条tree edge的两个顶点颜色都相反, 下面只需要检查non-tree edge.

最后遍历 $E$, 如果 $\forall e(u,v) \in E$, $u, v$的颜色都相反, 则 $G$ 是一个二分图. 否则不是.

复杂度 $O(|V|+|E|)$.

(b) Prove the following formulation: an undirected graph is bipartite if and only if it contains no cycles of odd length.

设 $A:G$ is bipartite; $B: G$ contains no cycles of odd length.

必要性:
$A \Rightarrow B$
反证法. 假设 $G$ 中存在某个奇数长度的环 $< v_1, v_2, \ldots, v_{2k+1} > $ 顺次相连. 令 $v_1$的颜色为red, 则这个环中所有奇数下标的顶点的颜色都为red, $v_1$ 的颜色与 $v_{2k+1}$ 的颜色相同了, 而 $v_1$ 又与 $v_{2k+1}$ 首尾相连, 所以 $G$ 不是二分图, 矛盾.

充分性:
$B \Rightarrow A$
看 $G$ 的 DFS 生成树. 设 root 的颜色为 red, 记 root 的层数为0, 则层1的所有节点为green….所有偶数层的颜色为red, 所有奇数层的颜色为green.
条件 $B$ 包含了两种可能:

$G$ 本来就没有环, 本来就是一棵树, 那么 DFS 过程肯定遍历了 $E$. 没有 non-tree edge. 显然 $G$ 是二分图.
$G$ 有若干个包含偶数个顶点的环. 取任意一个包含 $2k$ 个顶点的环 $< v_1, v_2, \ldots, v_{2k} > $ 来看, 这些顶点都在 DFS 生成树上, 而且仅有 $ e’(v_{2k}, v_1)$ 是需要检查的 non-tree edge.
$ e’(v_{2k}, v_1)$ 的两个点下标奇偶性不同, 所以是两种不同的颜色, 所以没有违反二部图的条件. 对于所有其他的长度为偶数的环也都是这个情况. 推出 $G$ 是二分图.

remark: 感觉证明充分性: $B \Rightarrow A$ 的时候已经达到了充要的程度了.

Problem 3.15

我理解的英文版题目的意思是: 现在图 $G(V,E)$ 内都是单向边, 请你给出一个线性时间的算法判断该图是否为强连通图.

(a) 记 $G^R$ 为将 $G$ 中所有边的方向取反后得到的反转图.

判断强连通图的算法:

Pick any node $s$ in $G$.
Run BFS from $s$ in $G$.
Run BFS from $s$ in $G^R$.
Return true iff all nodes reached in both BFS executions.

因为 BFS 耗费 $O(|V|+|E|)$ 的时间, 本算法跑了两遍 BFS, 所以本算法的时间复杂度也是 $O(|V|+|E|)$ . 换成 DFS 也是一样的.

(b)
记由hall出发可达的点集为 $h$ (用一个 bool型的大小为 $|V|$ 的一维数组记录), 只需要检查由 $h$ 的所有点出发能否返回 hall 就可以了. 稍微修改一下 (a) 中给出的算法:

Run BFS from hall in $G$. Add the visited vertices to $h$.
Run BFS from hall in $G^R$. Delete the visited vertices from $h$ (If it’s already in $h$).
If $h=\emptyset$, then return true; else return flase.

向点集 $h$ 中添加删除点都只需要 $O(1)$ 时间.
本算法的时间复杂度还是 $O(|V|+|E|)$ . 换成 DFS 也是一样的.

Problem 3.17

(a)

$\exists i, Inf(p) \subseteq SCC_i $ . 根据 SCC 的性质可知, $Inf(p)$ 一定可以画出一条无穷路径, 因为里面任意两点都是可达的.
$\forall i, Inf(p) \nsubseteq SCC_i $ . 设 $U \subset Inf(p) $ 且 $U \subseteq SCC_i$ , 即 $Inf(p)$ 的部分点集 $U$ 在某个SCC内部, 再设 $Inf(p)$ 除了 $U$ 还存在有一点 $v$ , $v$ 不在 $U$ 所处的 SCC中. 下面证明 $U$ 和 $v$ 同时出现无穷多次是不可能的. 根据 SCC 的定义, 从 $U$ 中的某个点出发, 一直在 $U$ 里面绕, $U$ 中的点似乎是可以出现无穷多次的. 但是一旦从 $U$ 到了 $v$, 就无法从 $v$ 再回去 $U$了 (若从 $v$ 可以再回去 $U$, 则 $v$ 也是 $U$ 所属的 SCC的一部分了, 不符合假设.) 也就是说, $U$ 只被访问了有限次后截止, 矛盾. $Inf(p)$ 除了 $U$ 还存在有更多点也是一样的不可能.
综上, $\exists i, Inf(p) \subseteq SCC_i $

(b)
就是判断 $G$ 里面有没有 SCC. 就是Decomposing a graph into its SCCs, 然后找是否存在某个SCC包含的点数大于或等于 2 的. 若存在, 则 $G$ 有无穷路径. 若不存在, 则 $G$ 没有无穷路径.
算法伪代码表述如下:

function split_scc(G):
    DFS( reverse of G)
    for v in V,  in decreasing order of reverse-of-G post numbers:
        if !visited[v]:
            explore(G, v)
            output nodes seen as an SCC

function solve_b:
    sccs = split_scc(G)
    for scc in sccs:
        if scc.size >= 2:
            return true
    return false

function solve_c:
    sccs = split_scc(G)
    for scc in sccs:
        if scc.size >= 2 && intersect(scc, good_vertices)!=∅:
            return true
    return false

(d)
算法伪代码表述如下:

function solve_c:
    sccs = split_scc(G)
    for scc in sccs:
        if intersect(scc, good_vertices).size >= 2:
            return true
    return false

Problem 3.25

(a) 先进行拓扑排序, 然后按拓扑顺序的逆序依次计算每个顶点，即设定待计算顶点的 cost 值为它自身的 $p$ 值与它的所有邻接点的 cost 值中的最小值.
(b) 先对有向图 $G$ 进行 SCC 的剖分(用课上讲过的算法). 显然一个 SCC 内的所有点的 cost 值都一样. 把每个 SCC 作为一个 meta-graph 看待, 就变成了第一问中的DAG, 可以用第一问的解法解题.

Problem 3.28

(a) $ x_1= \text{true}, x_2= \text{true}, x_3= \text{true}, x_4= \text{true} $
(b) $ (x_1 \lor x_2 )\land ( \overline x_1 \lor x_2 )\land (x_1 \lor \overline x_2 )\land (\overline x_1 \lor \overline x_2 )~ x_3,x_4 $随便了
(c) 所有连接关系如下:
$$
x_2 \to x_1 \
\overline x_1 \to \overline x_2\
x_1 \to \overline x_3\
x_3 \to \overline x_1\
\overline x_1 \to x_2\
\overline x_2 \to x_1\
x_3 \to x_4\
\overline x_4 \to \overline x_3\
x_1 \to x_4\
\overline x_4 \to \overline x_1
$$

(d) $x$ 和 $\overline x$ 在同一个 SCC 内 $\Rightarrow$ 从 $x$ 可达 $\overline x$ 并且从 $\overline x$ 可达 $x$. $\overline x$ 和 $x$二者必有一个为 true. true 的后继节点必然为 true, 而 $\overline x$ 和 $x$在一个环内, 这样推导下去得出二者都为 true, 矛盾.

(e) 2-SAT 条件 $\Leftrightarrow$ 对于图中的每一条边 $ e (u,v )$ , 如果 $u$ 为真，那么 $v$ 也为真. 假设 $G$ 不存在同时包含某个变量和它的“反”（即逻辑非）的 SCC，对于它的某个sink SCC来说，如果将这个SCC的所有顶点都设为真，这并不破坏逻辑图的相容性，因为sink SCC为真并不影响其它顶点的值，同时由于这些顶点的“反”为假，所以也不影响其子孙的值.

并且所有 sink SCC 的 negative literal 肯定不存在除他们自身以外的祖先. 因为 $p \to q \Leftrightarrow \overline q \to \overline p$. 若存在则那个点则 sink SCC会有一条出去的线, 这是不可能的.

(f) 按照上一问的过程处理即可

Problem 4.10

类似于 Bellman-Ford 算法，以 $u$ 为源点，每次 update 所有的边，循环 $k$ 次即可

function solve4_10(G, s):
    dist[s] = 0
    for u in V:
        dist[u] = ∞
        prev [u] = nil

    repeat k times:
        for e in E:
            update(e)

function update(e):
    (u,v) = e
    if dist[v] > dist[u]+l(u,v):
        dist[v] = dist[u]+l(u,v)

Problem 4.21

类似Bellman-Ford算法. 建立有向图 $G(V,E)$ , 用 dist[x] 表
示一个单位的 $s$ 币最多能换到多少个单位的 $x$ 币.
(a) 只需稍作修改update函数. 本题假设不存在下一问所说的异常情况.

function solve4_21a(G):
    dist[s] = 0
    for u in V:
        dist[u] = ∞
        prev [u] = nil

    repeat k times:
        for e in E:
            update(e)

function update(e):
    (u,v) = e
    if dist[v] > dist[u]*l(u,v):
        dist[v] = dist[u]*l(u,v)

(b) 类似于“负权回路”的情况. ，在 Bellman-Ford 算法完成之后，再对所有边进行一次 update 过程，如果有某个顶点的 money 值增加了，说明存在 anomaly.

function solve4_21b(G):
    solve4_21a(G)
    for e in E:
        if still_update(e):
             return true
    return false

function still_update(e):
    (u,v) = e
    if dist[v] > dist[u]*l(u,v):
        return true
    else:
        return false

Chapter5 Greedy algorithms

Problem 5.21

(a) 类似cut property的证明. 设题述的环的顶点集合为 $v$ , 最大权边为 $e(u_1, u_2)$. 设$v$ 被分割成两个部分 $s_1 , s_2$, 其中 $s_1$包含 $u_1$, $s_2$包含 $u_2$. 因为原来 $v$ 组成了一个环, 所以原来连接 $s_1 , s_2$ 的边至少有两条, 而且这两条边里面肯定至少存在一条比 $e$ 权值更小的边 $l$ (或 $v$ 上的边都相等, 更简单, 直接替换 $e$ ). 用 $l$ 替换 $e$ , 就得到了不包含 $e$ 的更小的一个 spanning tree.

(b) 因为每次删除的都是图 $G$ 中权最大的环边，由(a)中的性质可证.

(d)①对边集 $E$ 的 for 循环 $ = O(|E|)$;
②判断 $e$ 是否为某个cycle的一部分$ = O(|E|)$
总复杂度$ = O(|E^2|)$

Problem 5.22

(a) 显然对已形成的 MST 没有影响.
(b) 将 $e$ 加入 $T$ 中，形成一个环，将该环中权值最大的边去掉即可.
(c) $T$ 中 $e$ 的权值自然变小, 无需改变 $T$ 的结构
(d) 在图 $G$ 中找到 $e$ 所在的环 $r$（如果不存在则MST不变), 若 $w(r-e) < w(e)$ , 则用 $r-e$ 替换现存MST的 $e$.

Problem 5.32

类似于操作系统的短作业优先调度算法 (SJF Algorithm). 解决方案是把服务时间较短的顾客尽量排在前面.

设 ${t_i} = {a_i}, a_1 \leq a_2 \leq a_3 \ldots a_n$

证明:
我的思路是由一个随机序列 $t_1 \ldots t_n $ (记作 $L_n$. $L_x$意为未经整理的customer有 $x$ 个) 出发, 不断将 $t$ 值大的整理到队尾(因为这样得到的新 $T$ 比原来更小), 得到最优序列.
最初的 $T_0 = \sum_{i=1}^n (n-i+1)a_i$ ($T_i$ 意为已经整理了 $i$ 个customer的总等待时间).
在 $L_n$ 中找到 $a_n$ , 设 $a_n$ 在 $L_n$ 中排倒数第 $i$ 个, 如果 $a_n$ 不在倒数第一个, 则把 $a_n$ 换到队尾. 此时
$T_1 = n t_1 + (n-1)t_2 + \cdots +(i+1)t_{n-i} + i \times t_n +(i-1)t_{n-i+2} + \cdots + a_n $
有
$T_1 - T_0 = i(t_n - a_n) + a_n -t_n$
$ \because \forall i, a_n \geq t_i $
$ \therefore T_1 - T_0 \leq 0 $
因为 $L_n$ 是任意的一个随机序列, 所以当 $T$ 取min时, $a_n$ 必在队尾.

将 $a_n$ 整理到队尾后的序列为 $L_{n-1}$, 在其中找到 $a_{n-1}$, 同理可证调换到序列 $L_{n-1}$ 的尾部得到的 $T_2 \leq T_1$.

用同样的方法处理序列 $L_{n-2} , L_{n-3}, \ldots ,L_{1}, L_0 $
得到的 $L_0$ 即为总等待时间最短的序列, 此序列是按 $t_i$ 升序排列的.

<Ctrl+R row>

Problem 5.26

x = repeat(0) #x is an infinate list of integers all initialized to 0

n = 0; #the number of input variables for now
# i is the left  hand side variable's index
# j is the rignt hand side variable's index
# assume i<j
# if eq == True then i==j
def input(i, j, eq):
    if n<i:
        x[i] = x[n] + 1
        n +=2          # input 2 new variables at once
        if eq:
            x[j] = x[i]
        else:
            x[j] = x[i] + 1
        return True    #两个新的变量无论什么关系都可以满足
    if n<j: # i<=n && n<j
        if i==n:
            x[i] = x[n]
            n += 1
        else:
            x[i] = x[n] + 1
            n += 2
        if eq:
            x[j] = x[i]
        else:
            x[j] = x[i] + 1
        return True    #1个新的变量无论什么关系都可以满足
    if j<=n: # x[i], x[j] are already in the list
        relation = (x[i]==x[j])
        return relation==eq

Problem 5.28

数据结构:
可供选择的 $n$个人之间是否认识构成了一个图 $G(V, E)$, 其中$|V|=n$.
若第 $i$ 个人认识第 $j$ 个人, 则 $v_i$ 与 $v_j$ 直接相连;
若第 $i$ 个人不认识第 $j$ 个人, 则 $v_i$ 与 $v_j$ 不相连;

只需要遍历 $V$ , 逐个删除不满足Alice要求的点, 最终剩下的就是她能够邀请的最多的客人集合.

伪代码:


def invite(G(V, E)):
    for v in V:
        if connections of v < 5 || disconnections of v < 5 :
            G.delete(v)
    return G

Problem 5.33

复杂度分析:
把每个implication clause的左侧用list存储, 那么下面代码的第9行可以在 $O(1)$ 时间内完成. 对于伪码中的 W 的所有操作也可以在 $O(1)$ 时间内完成每个变元最多进入 W 一次, 从 W 中最多被删除一次. 所以, while循环的迭代次数最多就是变元数 $n$ .
每个形如 $(v_1 \land v_2 \cdots \land v_k ) \to v_{k+1} $的implication clause在伪码的最多被检查 $k$ 次. 所以第9,10两行总的执行次数上界为 $O(n)$ .

综上 FastGreedyHorn(H) 的时间复杂度为 $O(n)$ , $n$ 是输入的Horn formula的变元数量.

// H is the input Horn formula
function FastGreedyHorn(H):
    for each v in H: v = false
    W = {v: v appears on the right-hand side of an empty implication}
    while W != ∅:
        take (and delete) v from W
        v = true
        for each clause c where v appears on the left side:
            delete v from the left side of c
            if c becomes an empty implication:
                W.add(the right-hand side variable of c) //may  already in W

    return the current true assignment

Chapter6 Dynamic Programming

Problem 6.14

想象每次从大布料的一角剪下一块为服装产品$c_i$而设的大小为$a_i \times b_i$ 的布. 然后得到缺一角的大布料. 切下这一角有两种做法, 竖着摆放(vertically), 横着摆放(horizontally). 跟题干描述的每次一分为二, 分三次的结果是一样的, 但是这样考虑更容易实现递推.

Step 1: define subproblem
$P(w, h)$ = 在宽为 $w$ ，高为 $h$ 布料上所能得到的收益. 显然， $P(w, h) = P(h, w)$.

Step 2: express recursively
考虑每一次切割式样的两种情况,竖着切(vertically), 横着切(horizontally).
$$
\begin{align}
& P_h(w, h, i) = c_i + P(a_i, h-b_i) + P(w - a_i, b_i)+ P(w - a_i, h- b_i) \
& P_v(w, h, i) = c_i + P(b_i, h-a_i) + P(w - b_i, a_i)+ P(w - b_i, h- a_i) \
& P(w, h) = \max\limits_{1 \leq i \leq n} \max{P_h(w, h, i), P_v(w, h, i) }
\end{align}
$$

Step 3: base case
$$P(0, \cdot) = 0 \
P(\cdot, 0) = 0$$

Step 4: Order of solving subproblems
$$ w = 1,2 \ldots X \
h = 1,2 \ldots Y
$$